# 两数之和IV: https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        """
            这道题
            1. 首先使用深度优先，按照递增顺序遍历遍历每一个元素
            2. 遍历每一个元素 num， 求对应的 target - num,  这里直接从上往下，按照查找树了就是 二分查找
        """
        def binarySearch(origin, target):
            """ 进行查找 target - num """
            t = target - origin.val
            # 变量查找顺序是，先局部后全局，再闭包，后内部。 所以这里的root，就是根节点
            cur = root
            while cur:
                # 必须是不同的两个
                if cur.val == t and origin != cur:
                    return True
                elif cur.val > t:
                    cur = cur.left
                else:
                    cur = cur.right

            return False

        def dfs(root):
            if not root:
                return 
            # 下面代码可以优化为一句
            if dfs(root.left) or binarySearch(root, k) or dfs(root.right):
                return True
            # if dfs(root.left):
            #     return True
            # # 对每个顺序遍历元素，进行查找 target - num
            # if binarySearch(root, k):
            #     return True
            # if dfs(root.right):
            #     return True

            """
            还可以优化成这样
            def dfs(root):
                if not root: return False
            
                return dfs(root.left) or binarySearch(root, k) or dfs(root.right)
            """

        return dfs(root) is not None


# 深度优先遍历加上 hash  O(1)查找 
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        """
            使用深度优先加上hashSet， 类似I
        """
        
        hashSet = set()
        def dfs(root):
            if not root: return False

            if dfs(root.left):
                return True

            if k - root.val in hashSet:
                return True
            hashSet.add(root.val)

            if dfs(root.right):
                return True
        

        return dfs(root) is True


class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        """
            还可以这样简写，不过就不是 dfs遍历了
        """
        
        hashSet = set()
        def dfs(root):
            if not root: return False

            if k - root.val in hashSet:
                return True
            hashSet.add(root.val)

            # or 就是逻辑判断， 默认不成立返回一个 False
            return dfs(root.left) or dfs(root.right)
        
        return dfs(root)

        